package org.apache.commons.graph.algorithms.coloring

import org.apache.commons.graph.CommonsGraph.coloring
import org.apache.commons.graph.CommonsGraph.newUndirectedMutableGraph
import org.apache.commons.graph.algorithms.coloring.exception.NotEnoughColorsException
import org.apache.commons.graph.builder.AbstractGraphConnection
import org.apache.commons.graph.model.BaseLabeledEdge
import org.apache.commons.graph.model.BaseLabeledVertex
import org.apache.commons.graph.model.UndirectedMutableGraph
import org.apache.commons.graph.utils.GraphUtils
import org.junit.Assert
import org.junit.Test
import java.text.DecimalFormat
import java.text.NumberFormat
import java.util.logging.Logger

/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

/**
 *
 */
class GraphColoringBackTrackingTestCase

    : org.apache.commons.graph.algorithms.coloring.AbstractColoringTest() {
    /**
     * see [wiki](http://en.wikipedia.org/wiki/Crown_graph) for more details
     */
    @Test
    fun testCrawnGraph() {
        val g =
            UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>()

        GraphUtils.buildCrownGraph(6, g)

        val coloredVertices: ColoredVertices<BaseLabeledVertex, Int> = coloring(g).withColors(createColorsList(2)).applyingBackTrackingAlgorithm()
        Assert.assertNotNull(coloredVertices)
        Assert.assertEquals(2, coloredVertices.requiredColors.toLong())
        checkColoring(g, coloredVertices)
    }

    @Test
    fun testCromaticNumber() {
        val two = BaseLabeledVertex("2")

        val g: UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> =
            newUndirectedMutableGraph(object : AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>() {
                override fun connect() {
                    val one = addVertex(BaseLabeledVertex("1"))
                    addVertex(two)
                    val three = addVertex(BaseLabeledVertex("3"))

                    addEdge(BaseLabeledEdge("1 -> 2")).from(one).to(two)
                    addEdge(BaseLabeledEdge("2 -> 3")).from(two).to(three)
                    addEdge(BaseLabeledEdge("3 -> 1")).from(three).to(one)
                }
            })

        val coloredVertex = ColoredVertices<BaseLabeledVertex, Int>()
        coloredVertex.addColor(two, 2)

        val coloredVertices: ColoredVertices<BaseLabeledVertex, Int> =
            coloring(g).withColors(createColorsList(3)).applyingBackTrackingAlgorithm(coloredVertex)
        Assert.assertNotNull(coloredVertices)
        Assert.assertEquals(3, coloredVertices.requiredColors.toLong())
        Assert.assertEquals(2, coloredVertices.getColor(two))
        checkColoring(g, coloredVertices)
    }

    @Test
    fun testCromaticNumberBiparted() {
        val g1 = UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>()

        GraphUtils.buildBipartedGraph(100, g1)

        val coloredVertices: ColoredVertices<BaseLabeledVertex, Int> =
            coloring(g1).withColors(createColorsList(2)).applyingBackTrackingAlgorithm()
        Assert.assertNotNull(coloredVertices)
        Assert.assertEquals(2, coloredVertices.requiredColors.toLong())
        checkColoring(g1, coloredVertices)
    }

    @Test
    fun testCromaticNumberComplete() {
        val g1 =
            UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>()

        GraphUtils.buildCompleteGraph(100, g1)

        val coloredVertices: ColoredVertices<BaseLabeledVertex, Int> =
            coloring(g1).withColors(createColorsList(100)).applyingBackTrackingAlgorithm()
        Assert.assertNotNull(coloredVertices)
        Assert.assertEquals(100, coloredVertices.requiredColors.toLong())
        checkColoring(g1, coloredVertices)
    }

    @Test
    fun testCromaticNumberSparseGraph() {
        val g1 = UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>()
        for (i in 0..99) {
            g1.addVertex(BaseLabeledVertex(i.toString()))
        }

        val coloredVertices: ColoredVertices<BaseLabeledVertex, Int> =
            coloring(g1).withColors(createColorsList(1)).applyingBackTrackingAlgorithm()
        Assert.assertNotNull(coloredVertices)
        Assert.assertEquals(1, coloredVertices.requiredColors.toLong())
        checkColoring(g1, coloredVertices)
    }

    @Test
    fun testEmptyGraph() {
        val g =
            UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>()

        val coloredVertices: ColoredVertices<BaseLabeledVertex, Int> =
            coloring(g).withColors(createColorsList(1)).applyingBackTrackingAlgorithm()
        Assert.assertNotNull(coloredVertices)
        Assert.assertEquals(0, coloredVertices.requiredColors.toLong())
    }

    @Test(expected = NotEnoughColorsException::class)
    @Throws(NotEnoughColorsException::class)
    fun testNotEnoughtColorGraph() {
        val two = BaseLabeledVertex("2")

        val g: UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> =
            newUndirectedMutableGraph(object : AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>() {
                override fun connect() {
                    val one = addVertex(BaseLabeledVertex("1"))
                    addVertex(two)
                    val three = addVertex(BaseLabeledVertex("3"))

                    addEdge(BaseLabeledEdge("1 -> 2")).from(one).to(two)
                    addEdge(BaseLabeledEdge("2 -> 3")).from(two).to(three)
                    addEdge(BaseLabeledEdge("3 -> 1")).from(three).to(one)
                }
            })
        coloring(g).withColors(createColorsList(1)).applyingBackTrackingAlgorithm()
    }

//    @Test(expected = NullPointerException::class)
//    fun testNullColorGraph() {
//        val g = UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>()
//        coloring(g).withColors(null).applyingBackTrackingAlgorithm()
//    }

//    @Test(expected = NullPointerException::class)
//    fun testNullGraph() {
//        coloring(null as UndirectedGraph<BaseLabeledVertex?, BaseLabeledWeightedEdge<Double?>?>?).withColors(null)
//            .applyingBackTrackingAlgorithm()
//    }

    @Test
    @Throws(Exception::class)
    fun testSudoku() {
        val g1 = UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>()
        val grid = GraphUtils.buildSudokuGraph(g1)

        val sudoku: ColoredVertices<BaseLabeledVertex, Int> =
            coloring(g1).withColors(createColorsList(9)).applyingBackTrackingAlgorithm()
        Assert.assertNotNull(sudoku)
        checkColoring(g1, sudoku)
        Assert.assertEquals(9, sudoku.requiredColors.toLong())

        // Printout the result
        val sb = StringBuilder()
        val nf: NumberFormat = DecimalFormat("00")
        sb.append("\n")
        for (i in 0..8) {
            for (j in 0..8) {
                sb.append("| " + nf.format(sudoku.getColor(grid[i][j])) + " | ")
            }
            sb.append("\n")
        }
        Logger.getAnonymousLogger().fine(sb.toString())
    }

    @Test
    @Throws(Exception::class)
    fun testSudokuWithConstraints() {
        val g1 = UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>()
        val grid = GraphUtils.buildSudokuGraph(g1)

        val predefinedColor = ColoredVertices<BaseLabeledVertex, Int>()
        predefinedColor.addColor(grid[0][0], 1)
        predefinedColor.addColor(grid[5][5], 8)
        predefinedColor.addColor(grid[1][2], 5)

        val sudoku: ColoredVertices<BaseLabeledVertex, Int> =
            coloring(g1).withColors(createColorsList(9)).applyingBackTrackingAlgorithm(predefinedColor)
        Assert.assertNotNull(sudoku)
        checkColoring(g1, sudoku)
        Assert.assertEquals(9, sudoku.requiredColors.toLong())

        Assert.assertEquals(1, sudoku.getColor(grid[0][0]))
        Assert.assertEquals(8, sudoku.getColor(grid[5][5]))
        Assert.assertEquals(5, sudoku.getColor(grid[1][2]))

        // Printout the result
        val sb = StringBuilder()
        val nf: NumberFormat = DecimalFormat("00")
        sb.append("\n")
        for (i in 0..8) {
            for (j in 0..8) {
                sb.append("| ")
                sb.append(nf.format(sudoku.getColor(grid[i][j])))
                sb.append(" | ")
            }
            sb.append("\n")
        }
        Logger.getAnonymousLogger().fine(sb.toString())
    }
}
